Telecommunications channels often carry traffic that is multiplexed from several sources. For example, a 2.488 Gb/s SONET STS-48 channel carries 48 51.84 Mb/s SONET STS-1 channels that are time multiplexed on a byte-by-byte basis. That is, the channel carries bytes 1.1, 2.1, 3.1, . . . , 48.1, 1.2, 2.2, 3.2, . . . , 48.2, 1.3, 2.3, 2.3, . . . where n.m denotes byte m of subchannel n. Details of the SONET format can be found in Ming-Chwan Chow, Understanding SONET/SDH: Standards & Applications, Andan Pub, ISBN 0965044823, 1995 and in ANSI Standard T1.105-1995, as well as Telcorida (tm) Technologies, Inc. GR-253-CORE, Issue Sep. 3, 2000, each of which is incorporated by reference in its entirety.
An STS-1 SONET frame is a repeating structure of 810 bytes arranged into 9 rows of 90 columns. The frame structure is transmitted in row-major order. That is, all 90-bytes of row 0 are transmitted, then all 90 bytes of row 1, and so on. At higher multiplexing rates, each byte of the STS-1 frame is replaced by a number of bytes, one from each of several multiplexed sources. For example, at STS-48, 48 bytes, one from each of 48 STS-1 subframes, are transmitted during each column interval. In this case, the order of transmission is to send all 48 subframe bytes for one column before moving on to the next column and to send all of the columns of a row before moving on to the next row.
A digital cross connect is a network element that accepts a number of multiplexed data channels, for example 72 STS-48 channels, and generates a number of multiplexed output channels where each output channel carries an arbitrary set of the subchannels from across all of the input ports. For example, one of the STS-48 output channels may contain STS-1 channels from different input channels in a different order than they were originally input.
An example of digital cross connect operation is shown in FIG. 1. The figure shows a cross connect 30 with two input ports and two output ports. Each of these ports contains four time slots. Input port 1 (the top input port) carries subchannels A, B, C, and D in its four slots and input port 2 (the bottom port) carries subchannels E, F, G, and H in its four time slots. Each time slot of each output port can select any time slot of any input port. For example, output port 1 (top) carries subchannels H, D, F, and A from 2.4, 1.4, 2.2, 1.1 where x.y denotes input port x, timeslot y. Input timeslots must be switched in both space and time. The first time slot of output port 1, for example must be switched in time from slot 4 to slot 1 and in space from port 2 to port 1. Also, some time slots may be duplicated (multicast) and others dropped. Subchannel A, for example, appears in output time slots 1.4 and 2.2 and subchannel G is dropped, appearing on no output time slot.
A digital cross connect can be implemented in a straightforward manner by demultiplexing each input port, switching all of the time slots of all of the input ports with a space switch, and then multiplexing each output port. This approach is illustrated in FIG. 2. The four time slots of input port 1 are demultiplexed (Demux) in demultiplexers 32 so that each is carried on a separate line. All of these demultiplexed lines are then switched by a space switch 34 to the appropriate output time slots. Finally, a set of multiplexers (Mux) 36 multiplexes the time slots of each output channel onto each output port. This approach is used, for example, in the systems described in U.S. Pat. Nos. 3,735,049 and 4,967,405.
The space-switch architecture for a digital cross connect as shown in FIG. 2 has the advantage that it is conceptually simple and strictly non-blocking for arbitrary unicast and multicast traffic. However, it results in space switches that are too large to be economically used for large cross connects. For example, a digital cross connect with P=72 ports and T=48 time slots requires a PT×PT (3456×3456) space switch with P2T2=11,943,936 cross points.
A more economical digital cross connect can be realized using a time-space-time (T-S-T) switch architecture as illustrated in FIG. 3. Here each input port is input to a time-slot interchanger (TSI) 38. A TSI switches a multiplexed input stream in time by interchanging the positions of the time slots. To switch time-slot i to time-slot j, for example, slot i is delayed by T+j−i byte times. The multiplexed streams out of the input TSIs are then switched by a P×P space switch 40 that is reconfigured on each time slot. The outputs of this space switch are switched in time again by a set of output TSIs 42. This T-S-T architecture is employed, for example, by the systems described in U.S. Pat. Nos. 3,736,381 and 3,927,267.
An example of the operation of a T-S-T digital cross connect on the configuration of FIG. 2 is shown in FIG. 4. Here the TSI for input port 1 does not change the positions of its input time slots. The input TSI for port 2, however, reorders its time slots from E, F, G, H, to -, F, H, E. The G here is dropped as it is not used by any output ports. The space switch takes the outputs of the two input TSIs and switches them, without changing time slots, to create the streams A, F, H, D and A, B, C, E. Note that this involves a multicast of timeslot A to both outputs. Finally, the output TSIs reorder these streams to give the output streams H, D, F, A and E, A, B, C.
A three-stage T-S-T digital cross connect is logically equivalent to a 3-stage Clos network with P T×T input stages, T P×P middle stages, and P T×T output stages. To route a configuration of input time slots to output time slots on such a switch a middle-stage time slot must be assigned to each connection. This routing is described in detail in Clos, Charles, “A Study of Non-Blocking Switching Networks”, Bell System Technical Journal, March 1953, pp. 406–424, and V. E. Benes, “On Rearrangeable Three-Stage Connecting Networks”, The Bell System Technical Journal, vol. XLI, No. 5, Sep. 1962, pp. 1481–1492. These references show that a 3-stage Clos network, and hence a T-S-T digital cross connect, is rearrangeably non-blocking for unicast traffic but cannot, in general route multicast traffic.
A network is rearrangeably non-blocking, or rearrangeable, for unicast traffic, if for every input to output permutation, there exists an assignment of middle stage time slots that will route that permutation. A network is strictly non-blocking if an existing configuration can be augmented to handle any new connection between an idle input time slot and an idle output time slot without changing the time slots assigned to any existing connection.
From its input and output terminals, a rearrangeable network is indistinguishable from a strictly non-blocking network if its configuration changes are (1) aligned to the start of a frame and (2) frame synchronized so that all TSIs and space switches switch their configurations at the start of the same frame. Such frame synchronized switching is referred to as “hitless” because it does not hit or corrupt the contents of any frames. There is no impact of rearranging existing connections as long as such rearrangement is hitless. Thus, with hitless switching, there is little advantage to strictly non-blocking switches. Hitless switching is provided in Lucent 800 and 900 series digital cross connects (see www.chipcenter.com/telecommunications/mdp/webscan/mn00e/mn00e016.htm; and connectivity1.avaya.com/exchangemax/).
A grooming switch is a cross-connect switch that internally aggregates and segregates data for efficient traffic routing. Aggregation is the combining of traffic from different locations onto one facility. Segregation is the separation of traffic.
For instance, a SONET grooming switch having 72 STS-48 input and output ports with STS-1 granularity routes any of one of the 72×48=3,456 input STS-1 signals to any one of the 3,456 output STS-1s. Such a grooming switch is non-blocking for unicast traffic, where “blocking” occurs when an active input cannot be connected to an output.
Three-stage Clos networks are often used in building grooming switches in order to minimize the number of crosspoints. A symmetric three-stage Clos network, C(n, m, r), has r n×m input switches, m r×r middle-stage switches, and r m×n output switches. Clos networks can be recursive. That is, each switch in a Clos network can be either a single-stage non-blocking crossbar or a three-stage Clos network.
A Clos network with an internal switch core speed-up of two, i.e., where m=2n, supports strictly non-blocking unicast traffic and rearrangeably non-blocking dualcast traffic (See C. Clos, “A Study of Non-Blocking Switching Networks,” Bell System Technical Journal, vol. 32, 406–424, 1953 and V. E. Benes, Mathematical Theory of Connecting Networks and Telephonic Traffic, New York: Academic Press, 1965, each of which is incorporated herein by reference.
FIG. 5 illustrates a TST (time-space-time) grooming switch 2 as a symmetric Clos network C(n, 2n, r), with the time-slot interchanges (TSIs) 4, 8 represented as horizontal planes and the time-multiplexed middle-stage crossbar 6 represented as vertical planes. Specifically, this TST grooming switch has r n×2n input TSIs 4, r 2n×n output TSIs 8, and an r×r 2n-time-multiplexed crossbar 6, where r is the number of ports and n is the number of time-slots per port.
For example, Velio Communications, Inc.'s VC2002 (tm) is a 72×72 time-space-time (TST) grooming switch, is implemented as a symmetric 3-stage Clos C(48, 96, 72) network with 72 input ports, 72 output ports, 48 time slots for each port, and 96 middle-stage time slots.
A general problem with TST switches is that they block arbitrary multicast traffic. On the other hand, a single-stage switch, effectively an nr×nr crossbar, is strictly non-blocking for arbitrary multicast traffic; that is, any available input can connect to any set of available outputs without disturbing existing connections. However, single-stage switches are expensive to implement.